package com.sparrow.common.ai.findpath.impl;

import com.sparrow.common.ai.findpath.Point;
import java.util.*;

/**
 * dijkstra 基于贪心算法的 最短路径,优先找移动成本低的路径。跟A*想比 要探索更多格子
 */
public class Dijkstra {

    /**
     * 这是一个优先级队列，路径成本最低的点在最前面
     */
    private PriorityQueue<Point> frontier;

    /**
     * 邻居
     */
    private List<Point> neighbors = new ArrayList<>(4);
    /**
     * 来源
     */
    private Map<Point, Point> cameFroms = new HashMap<>();
    /**
     * 每个点对应的移动成本
     */
    private Map<Point, Integer> costs = new HashMap<>();
    /**
     * 起点
     */
    private Point start;
    /**
     * 目标点
     */
    private Point goal;
    /**
     * 地图数据
     */
    private int[][] mapData;

    public Dijkstra(int[][] mapData) {
        this.mapData = mapData;
    }

    public void start(Point start, Point goal) {
        costs.put(start, 0);
        frontier = new PriorityQueue<>(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return costs.getOrDefault(o1, 0) - costs.getOrDefault(o2, 0);
            }
        });
        frontier.add(start);
        this.goal = goal;
        this.start = start;

        while (!frontier.isEmpty()) {
            //优先找成本最小的
            Point point = frontier.remove();
            if (point.equals(goal)) {
                break;
            }
            for (Point n : neighbors(point)) {
                int newCost = costs.get(point) + cost(point, n);
                if (!costs.containsKey(n) || newCost < costs.get(n)) {
                    costs.put(n, newCost);
                    frontier.add(n);
                    cameFroms.put(n, point);
                }
            }
        }
    }

    private int cost(Point point, Point next) {
        if (mapData[next.getY()][next.getX()] == 1) {
            return 10;
        }
        return 1;
    }

    public List<Point> neighbors(Point start) {
        neighbors.clear();
        int x = start.getX();
        int y = start.getY();
        if (y - 1 >= 0) {
            neighbors.add(new Point(x, y - 1));
        }
        if (x - 1 >= 0) {
            neighbors.add(new Point(x - 1, y));
        }
        if (y + 1 < mapData.length) {
            neighbors.add(new Point(x, y + 1));
        }
        if (x + 1 < mapData[0].length) {
            neighbors.add(new Point(x + 1, y));
        }
        return neighbors;
    }

    public List<Point> getPath() {
        Point pre = goal;
        LinkedList<Point> paths = new LinkedList<>();
        paths.add(pre);
        while (pre != null && !pre.equals(start)) {
            pre = cameFroms.get(pre);
            paths.add(pre);
        }

        Collections.reverse(paths);
        return paths;
    }

//    public static void main(String[] args) {
//        int[][] mapData = new int[10][10];
//        for (int i = 0; i < 10; i++) {
//            for (int j = 0; j < 10; j++) {
//                mapData[i][j] = 0;
//            }
//        }
//        MapFrame mapFrame = new MapFrame(mapData);
//        Dijkstra kernel = new Dijkstra(mapData);
//        Point start = new Point(0, 0);
//        Point goal = new Point(5, 5);
//        kernel.start(start, goal);
//
//        mapFrame.setPath(kernel.getPath().stream().map(e -> e.toIntArray()).collect(Collectors.toList()));
//
//    }
}
